﻿/*
* Copyright (c) 2010-2012 Tesla Engine Group
* 
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
* 
* The above copyright notice and this permission notice shall be included in
* all copies or substantial portions of the Software.
* 
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
* THE SOFTWARE.
*/


using System.Collections.Generic;

namespace Tesla.Util {
    /// <summary>
    /// Utilitiy containing sorting methods.
    /// </summary>
    public static class SortHelper {
        private static readonly int INSERTION_SORT_THRESHOLD = 7;

        /// <summary>
        /// Merge sort implementation. Uses insertion if the number of elements to sort is low.
        /// </summary>
        /// <typeparam name="T">Element type</typeparam>
        /// <param name="src">The source array</param>
        /// <param name="dest">The destination array that contains the sorted elements.</param>
        /// <param name="low">The lower bound.</param>
        /// <param name="high">The upper bound</param>
        /// <param name="offset">The offset from the start of the arrays</param>
        /// <param name="comp">The comparator to use</param>
        public static void MergeSort<T>(T[] src, T[] dest, int low, int high, int offset, IComparer<T> comp) {

            //Use insertion sort on small arrays
            int length = high - low;
            if(length < INSERTION_SORT_THRESHOLD) {
                for(int i = low; i < high; i++) {
                    for(int j = i; j > low && comp.Compare(dest[j - 1], dest[j]) > 0; j--) {
                        T temp = dest[j];
                        dest[j] = dest[j-1];
                        dest[j-1] = temp;
                    }
                }
                return;
            }

            //Merge sort: Recursively sort each half of dest into src
            int destLow = low;
            int destHight = high;
            low += offset;
            high += offset;
            int mid = (low + high) >> 1;
            MergeSort(dest, src, low, mid, -offset, comp);
            MergeSort(dest, src, mid, high, -offset, comp);

            //If list is already sorted, copy from src to dest
            if(comp.Compare(src[mid - 1], src[mid]) <= 0) {
                System.Array.Copy(src, low, dest, destLow, length);
            }

            //Merge sorted halves (now in src) into dest
            for(int i = destLow, p = low, q = mid; i < destHight; i++) {
                if(q >= high || p < mid && comp.Compare(src[p], src[q]) <= 0) {
                    dest[i] = src[p++];
                } else {
                    dest[i] = src[q++];
                }
            }
        }
    }
}
